class Solution {
    int ans = 0;
    int lr[301][301];   // 统计左边有多少个连续 '1'
    int ud[301][301];   // 统计上边有多少个连续 '1'
    // dp
    int dp[301][301];
    void check(vector<vector<char>>& matrix, int i, int j)
    {
        int up = ud[i][j], left = lr[i][j];
        int prev = 0;

        if(i - 1 >= 0 && j - 1 >= 0)
            prev = dp[i - 1][j - 1];
        
        dp[i][j] = min(min(up, left), prev + 1);
        ans = max(ans, dp[i][j]);
    }

public:
    int maximalSquare(vector<vector<char>>& matrix) {
        // dp[i][j]表示以i，j位置结尾能组成的最大正方形面积
        // 前提是i，j这个位置必须是 '1' 才有可能
        int m = matrix.size(), n = matrix[0].size();

        memset(lr, 0, sizeof(lr));
        memset(ud, 0, sizeof(ud));
        memset(dp, 0, sizeof(dp));

        // 先搞定 lr 和 ud
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(matrix[i][j] == '0')
                    continue;
                
                // '1'位置
                if(i != 0)
                    ud[i][j] = ud[i - 1][j] + 1;
                else
                    ud[i][j] = 1;

                if(j != 0)
                    lr[i][j] = lr[i][j - 1] + 1;
                else
                    lr[i][j] = 1;
            }
        }


        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(matrix[i][j] == '0')
                    continue;

                check(matrix, i, j);
            }
        }

        return ans * ans;   // 返回的是面积，需要乘方
    }
};

